Batch 2 - Class 38 - Sorting

• From prior class, recall that searching a sorted list is much faster than searching an unsorted list. Examples such as dictionaries
• Give kids 8 playing cards each in small groups, and introduce a notion of "comparison" with face down. Ask them to do successive comparisons to sort
• One person from the group will present how they sorted, and how many comparisons did they require
• Selection Sort: Introduce the idea of selection sort, and ask each group to now apply selection sort to their jumbled deck of cards, and count number of comparisons
• Ask students how many comparisons would it take for 4 cards? For 2?
• Selection sort essentially finds the smallest number, and then the problem is left to sorting (n-1) numbers. Is there a better way to do this partitioning?
• Quick Sort: Let us try random partitioning and count the number of comparisons
• Voila! Fewer?
• Why? Let kids discover why it takes fewer comparisons?
• When would the number of comparisons be lowest? When you they be highest?
• Can we force the partitions to be equal without worrying about the central number, and then later merge? Ask kids to do and figure out the number of comparisons - Merge Sort
• Introduce the notion of parallel computers - what if we can make a number of comparisons in parallel. Then could we sort even faster? How fast?
• Draw a Sorting Network for 8 numbers, and get kids to sort on that network

• How long does it take to sort on a sorting network?
• Ask kids to draw a sorting network for 16 items
• Discuss the time taken on each of the above as number of items to be scaled goes up - 100, 1000, 1000000?

• On a 4x4 chessboard, place 3 wolves and 2 sheep so that all the sheep are safe from being eaten by the wolves. 
• On a 5x5 chessboard, place 5 wolves and 3 sheep 
• Generalize! What about w wolves and s sheep on an n by n board?
• 
  
• Draw an alternate sorting network compared to the one discussed in class, say for selection sort or quick sort